class Solution(object):
    def smallestDistancePair(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def get_less_num(nums, diff):
        #获取nums中距离对小于等于diff的个数
            count = 0
            left = 0
            for right in range(len(nums)):
                while nums[right] - nums[left] > diff:
                    left = left + 1
                count += right - left
            return count

        nums_sorted = sorted(nums)
        #解空间[0, nums[-1] - nums[0]]
        l = 0
        h = nums_sorted[-1] - nums_sorted[0]
        #在l，h中二分查找
        while l < h:
            m = l + (h - l) / 2
            #判断<= m的距离对的个数是否等于k-1
            less_nums = get_less_num(nums_sorted, m)
            if less_nums >= k:
                h = m
            else:
                l = m + 1
        return l
